- Turing-Maschine
- Tu|ring|ma|schi|ne auch: Tu|ring-Ma|schi|ne 〈[tju:-] f. 19〉 theoretisches Modell einer Rechenmaschine mit unendlich großem Speicher, in dem sich diese von ihrer momentanen Position nur um eine Position vor od. zurück bewegen kann [nach dem engl. Mathematiker Alan Mathison Turing, 1912-1954]
* * *
Turing-Maschine,abstraktes Modell eines Automaten, anhand dessen grundsätzliche Aussagen über die Fähigkeiten beliebiger Rechenmaschinen gewonnen werden können. Das Modell wurde erstmals von Alan M. Turing im Jahr 1936 veröffentlicht. Eine Turing-Maschine besteht aus vier Komponenten:- ein Schaltwerk, das eine endliche Zahl von Zuständen einnehmen kann,- ein Speicherband, das unendlich lang ist und aus nebeneinander angeordneten Speicherzellen besteht, die entweder leer sind oder einen Buchstaben aus einem Alphabet mit endlich vielen Zeichen enthalten,- einen Schreib-/Lesekopf, der den Inhalt einer Zelle liest und/oder überschreibt oder auch unverändert lässt.Die Steuerung der Turing-Maschine geschieht über eine sog. Zustandsänderungstabelle, die für jeden Zustand angibt, welches der Zeichen des Alphabets welche Aktion (Schreiben, Lesen, Bewegen, Verändern des Maschinenzustands) auslöst. Wird die Turing-Maschine gestartet, so liest sie zunächst das Zeichen an der aktuellen Position des Schreib-/Lesekopfs und führt dann die in der Tabelle für dieses Zeichen und den momentanen Maschinenzustand aufgeführte Aktion durch.Jede Turing-Maschine stellt (zusammen mit ihrer Zustandsänderungstabelle) einen speziellen Algorithmus dar. Ein Algorithmus ist nach Turing und dem US-amerik. Logiker A. Church genau dann berechenbar, wenn die zugehörige Turing-Maschine nach endlich vielen Schritten anhält (churchsche These). Diese Hypothese ist bis heute zwar nicht bewiesen, wird jedoch allgemein als gültig angenommen.
Universal-Lexikon. 2012.
